// https://www.lintcode.com/problem/evaluate-reverse-polish-notation/description
// 解析运算表达式、
// 424. 逆波兰表达式求值
// 求逆波兰表达式的值。

// 在逆波兰表达法中，其有效的运算符号包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰计数表达。

// 样例
// ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
// ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6


• ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
• ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
• 栈在表达式求值中的运用
• 遇到数字直接push进栈
• 遇到+ - * /时pop出栈顶2个数并相应运算求值，结果push进栈


class Solution {
public:
    /**
     * @param tokens: The Reverse Polish Notation
     * @return: the value
     */
    int evalRPN(vector<string> &tokens) {
        stack<int> nodes;
        int num1, num2;
        for (int i = 0; i < tokens.size(); i++)
        {
            if (tokens[i] != "+" && tokens[i] != "-" 
            && tokens[i] != "*" && tokens[i] != "/")
            {
                nodes.push(stoi(tokens[i]));
            }
            else
            {
                // num1 = nodes.top();
                num2 = nodes.top();
                nodes.pop();
                // num2 = nodes.top();
                num1 = nodes.top();
                nodes.pop();
                if (tokens[i] == "+")
                {
                    nodes.push(num1 + num2);
                }
                else if (tokens[i] == "-")
                {
                    nodes.push(num1 - num2);
                }
                else if (tokens[i] == "*")
                {
                    nodes.push(num1 * num2);
                }
                else if (tokens[i] == "/")
                {
                    nodes.push(num1 / num2);
                }
            }
        }
        return nodes.top();
    }
};